package SwordFingerOffer;

import java.util.HashSet;
import java.util.Set;

public class Q48_LongestNoRepeatSubString {

    //最长不重复子串
    //请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

    //纯暴力枚举
    public int lengthOfLongestSubstring(String s) {
        char[] str = s.toCharArray();
        int max = 0;
        for (int i = 0; i < str.length; i++) {
            int time = process(str, i);
            max = Math.max(time, max);
        }
        return max;
    }


    //此字符之后 - 不含重复的长度
    public int process(char[] str, int index) {
        Set<Character> set = new HashSet<>();
        for (int i = index; i < str.length; i++) {
            if (set.contains(str[i])){
                return set.size();
            }
            set.add(str[i]);
        }
        return set.size();
    }

    //滑动窗口 + HASHSET  ==> O(N) + O(N)
    public int Windows(String s){

        char[] str = s.toCharArray();
        Set<Character> set = new HashSet<>();
        int left = 0;
        int right = 0;
        int max = 0;
        while (left != str.length && right != str.length){
            if (!set.contains(str[right])){
                set.add(str[right]);
                //结算
                right++;
                max = Math.max(max, right - left);

            }else {
                //重复了
                //跳到重复位置的下一跳
                for (int i = left; i < right; i++) {
                    if (str[i] == str[right]){
                        left = i + 1;
                        //还要让 right 再结算一遍，所以抵消上面的 right++
                        //right--;
                        set.remove(str[right]);
                        break;
                    }
                    set.remove(str[i]);
                }
            }
        }
        return max;
    }


    public static void main(String[] args) {
        Q48_LongestNoRepeatSubString fun = new Q48_LongestNoRepeatSubString();
        System.out.println(fun.Windows("abba"));
    }
}
